/*邻接矩阵的C语言描述*/
typedef struct
{ // 图的定义
	VertexType vexs[MAX_VERTEX_NUM];  // 存储顶点信息                    
 	EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵，存储边的信息                     
	int vexnum, arcnum;   // 顶点数，边数      
	GraphKind kind;     // 图的种类标志             
} MGraph;

/*邻接表的C语言描述*/
typedef struct ArcNode //边的结点结构
{  
	int adjvex;   // 该边所指向的顶点的位置
	struct ArcNode *nextarc;  // 指向下一条边的指针
} ArcNode;
typedef struct VNode	//顶点的结点结构
{ 
	VertexType  data;    // 顶点信息
	ArcNode  *firstarc;  // 指向第一条依附于该顶点的边
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct 
{  
	AdjList vertices;
	int vexnum, arcnum; //顶点数、边数
	GraphKind kind;   // 图的种类标志
} ALGraph;

/*深度优先遍历*/
	//连通图
void DFS(Graph G, int v)	// 从顶点v出发，深度优先搜索遍历连通图G
{
	visited[v] = TRUE;
	VisitFunc(v);
	for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w))
	{
		if (!visited[w])  // 对v的尚未访问的邻接顶点w递归调用DFS
			DFS(G, w);
	}
} // DFS

	//非连通图
void DFSTraverse(Graph G)	// 对图 G 作深度优先遍历。
{
	for (v=0; v<G.vexnum; ++v) 
		visited[v] = FALSE; //访问标志数组初始化
	for (v=0; v<G.vexnum; ++v) // 对尚未访问的顶点调用DFS
	{
		if (!visited[v])
			DFS(G, v);
	}
}

/*广度优先遍历*/
void BFSTraverse(Graph G) 
{
	for (v=0; v<G.vexnum; ++v)
		visited[v] = FALSE;  //初始化访问标志
	InitQueue(Q);       // 置空的辅助队列Q
	for ( v=0;  v<G.vexnum; ++v )
	{
		if ( !visited[v]) // v 尚未访问
		{ 
			visited[v] = TRUE;	VisitFunc(v);    // 访问v
			EnQueue(Q, v);             // v入队列
			while (!QueueEmpty(Q))
			{
				DeQueue(Q, u);    // 队头元素出队并置为u
				for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w))
					if ( ! visited[w])
					{
						visited[w]=TRUE;  VisitFunc(w);
						EnQueue(Q, w); // 访问的顶点w入队列
					} // if
			} // while
		} 
	}
} // BFSTraverse

	/*拓扑排序*/
/*	
	取入度为零的顶点v;
	while (v != 0) 
	{
		printf(v);  ++m; //输出顶点，顶点计数增1
		w = FirstAdj(v); //取v邻接点
		while (w != 0) 
		{
			inDegree[w]--; //删除边
			w = nextAdj(v,w); //取下一邻接点
		}
		取下一个入度为零的顶点v;
	}
	if (m<n)
		printf(“图中有回路”); //顶点未全输出
*/
CountInDegree(G,indegree);//对各顶点求入度
InitStack(S);
for ( i=0; i<G.vexnum; ++i)
{
	if (!indegree[i])  
		Push(S, i);
                              //入度为零的顶点入栈
}
count=0;           //对输出顶点计数
while (!EmptyStack(S)) 
{
	Pop(S, v);  
	++count;  
	printf(v);
	for (w=FirstAdj(v); w; w=NextAdj(G,v,w))
	{
		--indegree[w];  // 弧头顶点的入度减一
		if (!indegree[w])	//新产生的入度为零的顶点入栈
			Push(S, w);             
	}
}
if (count<G.vexnum) 
	printf(“图中有回路”);

